package org.hot100_3;

public class leetcode5 {
    public String longestPalindrome(String s) {

        int n = s.length();

        boolean[][] dp = new boolean[n][n];

        dp[0][0] = true;

        int maxLength = 1;
        String maxStr = s.substring(0, 1);

        for (int right = 1; right < n; right++) {
            for (int left = 0; left < right; left++) {
                if (s.charAt(left) == s.charAt(right)) {
                    //right-left<=2表示，left和right对应的字符相等，并且两者之间存在1个或者0个元素
                    //如aba 和 aa
                    if (dp[left + 1][right - 1] || right - left <= 2) {
                        dp[left][right] = true;

                        if (right - left + 1 > maxLength) {
                            maxLength = right - left + 1;
                            maxStr = s.substring(left, right);
                        }
                    }
                }
            }
        }

        return maxStr;
    }
}
